package 每日一题;

public class 最大正方形 {
    public static int maximalSquare(char[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp=new int[m][n];
        int res=0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
             if(matrix[i][j]=='1'){
                 if(i==0||j==0){
                     dp[i][j]=1;
                 }else {
                     dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                 }
             }
             res=Math.max(dp[i][j],res);
            }
        }
        return res*res;
    }

    public static void main(String[] args) {
        char[][] matrix={{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        //char[][] matrix={{'1','1'},{'1','1'}};
        System.out.print(maximalSquare(matrix));
    }
}
